package com.cat.dataStructure02;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-subsequence-score/
 * @create 2025/10/27 20:37
 * @since JDK17
 */

public class Solution72 {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        long ans = 0, sum = 0;

        int n = nums1.length;
        int[][] arr = new int[n][2];
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            arr[i] = new int[]{nums2[i], nums1[i]};
        }
        Arrays.sort(arr, Comparator.comparing(row -> row[0]));  // 根据nums排升序
        for (int i = n - 1; i > n - k; i--) {
            heap.add(nums1[i]);
            sum += nums1[i];
        }
        for (int i = n - k; i >= 0; i--) {
            ans = Math.max(ans, arr[i][0] * (sum + arr[i][1]));
            int x = heap.poll();
            if (x < arr[i][1]) {
                heap.add(arr[i][1]);
            } else {
                heap.add(x);
            }
        }

        return ans;
    }
}
